\documentclass{article}
\usepackage{amsmath,amsfonts}
\usepackage{latexsym}
\usepackage{bbm}
\usepackage[pdftex]{graphicx}
\usepackage[framed,numbered]{mcode} % MATLAB code typesetting package (credit: Florian Knorn)


\marginparwidth 0pt
\oddsidemargin  0pt
\evensidemargin  0pt
\marginparsep 0pt
\topmargin   0pt
\textwidth   6.0in
\textheight  8.5in

\begin{document}

\begin{flushright}
{\bf Andrew Ziegler\\Siva Subramaniam\\
May 23, 2011\\
CSE 252C\\
Assignment \#2\\
}
\end{flushright}

Note: All Matlab code was typeset using \cite{lib:mcode}

\begin{enumerate}

\item Dimensionality reduction on the MNIST database.
\begin{enumerate}
\item Generate a random projection matrix $G\in{\mathbb R}^{d'\times d}$ with entries $G_{ij}\sim {\mathcal N}(0,1/d')$.  Use $d'=49$, which represents a factor of 16 smaller than the full dimensionality ($d=784$).  Compute the mean squared difference between the entries of $G^\top G$ and a $d\times d$ identity matrix.  It should be close to $1/d'$.
\item Compute the ROC curve as in Homework \#1 problem 3 using $L_2$ distances on $G\boldsymbol{x}^i$ in place of $\boldsymbol{x}^i$.  How does the new EER compare to the old one?
\item Repeat the preceding step with a different dimensionality reduction method of your choice, keeping $d'$ fixed.
\end{enumerate}

\item Mahalanobis distance.

The {\em Mahalanobis distance} between $\boldsymbol{x}^i$ and $\boldsymbol{x}^j$ is given by $\Delta^2=(\boldsymbol{x}^i-\boldsymbol{x}^j)^\top\Sigma^{-1}(\boldsymbol{x}^i-\boldsymbol{x}^j)$, where $\Sigma$ is a $d\times d$ covariance matrix.
\begin{enumerate}
\item A covariance matrix $\Sigma$, by definition, is symmetric and positive definite, which means $\boldsymbol{a}^\top\Sigma \boldsymbol{a}>0$ for all $\boldsymbol{a}\in {\mathbb R}^d$.  Show that a necessary and sufficient condition for $\Sigma$ to be positive definite is that all of its eigenvalues are positive.
\item $\Delta^2$ is equivalent to the squared Euclidean distance between $\boldsymbol{y}^i$ and $\boldsymbol{y}^j$, where $\boldsymbol{y}$ is a linearly transformed version of $\boldsymbol{x}$.  What is that transformation?
\item Give an example of an application for which Mahalanobis distance is appropriate (e.g., compared to $L_2$ distance) and explain intuitively what $\Sigma^{-1}$ captures in this case.
\end{enumerate}

\item Properties of Chi Squared distance.

Recall that the $\chi^2$ distance is given by $\chi^2_{ij}=\frac{1}{2}\sum_{k=1}^d(x_k^i-x_k^j)^2/(x_k^i+x_k^j)$ where the $\boldsymbol{x}$'s are normalized histogram vectors.  Prove or disprove the following statements:

\begin{enumerate}
\item $\chi^2_{ij}\in[0,1]$.
\item The matrix $Q\in {\mathbb R}^{n\times n}$ with entries $Q_{ij}=\sum_{k=1}^dx_k^ix_k^j/(x_k^i+x_k^j)$ is positive definite.
\item  $\chi^2_{ij}$ is a metric.
\end{enumerate}

\item Gabor Functions.

The expression for the (unnormalized) isotropic 2D Gabor function is given by a Gaussian times a complex exponential
\[
h({\boldsymbol{x}})=e^{-\| {\boldsymbol{x}} \|^2/2\sigma^2}e^{j 2\pi {\boldsymbol{u}}_o^\top {\boldsymbol{x}}}
\]
where $\boldsymbol{x}=(x,y)^\top$ and $\boldsymbol{u}_o=(u_{o},v_{o})^\top$, and it
serves as an oriented bandpass filter.  The even and odd Gabor
functions are equal to the real and imaginary parts of $h$,
respectively.

\begin{enumerate}
\item Compute four examples of even and/or odd 2D
Gabor functions on the interval $\boldsymbol{x}\in[-14,13]\times[-14,13]$
using parameters chosen in the following ranges: $\sigma\in[1,3]$ and
$\boldsymbol{u}_o\in[0,0.3]\times[0,0.3]$.  For each example, display the function as an image and as a surface plot.

\item Apply the above set of filters to two different MNIST digits and display the results.  Select a few of the filtered images to explain what the filter responses are responding to in the input images. 

\end{enumerate}


\end{enumerate}


\end{document}







